package org.algorithm.熊猫.链表;

import org.algorithm.common.ListNode;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/***
 *
 *  和为0 包括但不限定：    正整数之间想减和为0， 正负相加和为0
 *
 * 参考地址： https://leetcode-cn.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/
 */
public class 删除和为0的连续节点 {

    @Test
    public void test() {
        ListNode node = ListNode.build(9, 1, 1, 2, -3);
        System.out.println();
        ListNode.print(removeZeroSumSublists(node));
    }

    public ListNode removeZeroSumSublists(ListNode head) {
        //创建哨兵节点
        ListNode sentry = new ListNode(0);
        sentry.next = head;

        //创建map将所有出现的结果保存
        Map<Integer, ListNode> map = new HashMap<>();
        // 统计累加数
        // 出现两次同一数值则说明 两次中间和为0，记录最后一次的位置
        int sum = 0;
        for (ListNode h = sentry; h != null; h = h.next) {
            map.put(sum += h.val, h);
        }
        // 第二遍遍历 若当前节点处sum在下一处出现了，则表明两结点之间所有节点和为0 《《直接删除区间所有节点》》
        // 如果没有总和为零的相邻节点，则map.get(sum)的值与当前h值相同
        sum = 0;
        for (ListNode h = sentry; h != null; h = h.next) {
            sum += h.val;
            h.next = map.get(sum).next;
        }
        return sentry.next;
    }
}
